package com.jietuo.class02;

/**
 * @author zhangx & jietuo_zx@163.com
 * @version 1.0
 * @date 2024/3/1
 * @description: 1，单项链表和双向链表反转
 */
public class Code01_LinkedReversal {


    // 单链表反转，node01 -> node02 -> node03
    // ==>       node03 -> node02 -> node01
    public static Node nodeReversal(Node head) {
        // 如果为空或者链表只有一个元素，则直接返回
        if (head == null || head.next == null) {
            return head;
        }
        Node pre = null;
        Node next = null;
        while (head != null) { //head = node01    // node02
            next = head.next; //next = node02     next = node02
            head.next = pre; // head.next = null; head.next = node01
            pre = head;  // pre = node01;         pre = node02
            head = next; // head = node02 往下移   head = node03
        }
        return pre;
    }


    // 双向链表反转，node01 <-> node02 <-> node03
    // ==>       node03 <-> node02 <-> node01
    public static DoubleNode doubleNodeReversal(DoubleNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        DoubleNode pre = null;
        DoubleNode next = null;
        while (head != null) {  // head node01
            next = head.next;  // next node02
            head.next = pre;  // node01.next = null
            head.pre = next;  // head.pre = node02
            pre = head;  // pre = node01
            head = next; // head = node02
        }
        return pre;

    }


    public static void main(String[] args) {
        Node node01 = new Node(1);
        Node node02 = new Node(2);
        Node node03 = new Node(3);
        Node node04 = new Node(4);
        node01.next = node02;
        node02.next = node03;
        node03.next = node04;
        node04.next = null;
        Node.printNode(node01);
        Node nodeReversal = nodeReversal(node01);
        Node.printNode(nodeReversal);

        System.out.println("=======");

        DoubleNode doubleNode01 = new DoubleNode(1);
        DoubleNode doubleNode02 = new DoubleNode(2);
        DoubleNode doubleNode03 = new DoubleNode(3);
        DoubleNode doubleNode04 = new DoubleNode(4);
        doubleNode01.next = doubleNode02;
        doubleNode01.pre = null;
        doubleNode02.next = doubleNode03;
        doubleNode02.pre = doubleNode01;
        doubleNode03.next = doubleNode04;
        doubleNode03.pre = doubleNode02;
        doubleNode04.next = null;
        doubleNode04.pre = doubleNode03;

        DoubleNode.printDoubleNode(doubleNode01);
        DoubleNode doubleNodeReversal = doubleNodeReversal(doubleNode01);
        DoubleNode.printDoubleNode(doubleNodeReversal);

    }
}
